package leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author Administrator
 * @description
 * @date 2023/3/16 0016
 */
public class Solution10 {

    private int[] memo;
    public int numWays(int n) {
        memo = new int[n+1];
        Arrays.fill(memo, -1);
        return dp(n);
    }

    private int dp(int n) {
        if (memo[n] != -1) {
            return memo[n];
        }
        if (n == 1 || n == 0) {
            return 1;
        }
        memo[n] = (dp(n-1)+dp(n-2))%1000000007;
        return memo[n];
    }
}
